# 给定一个链表，判断链表中是否有环。 
# 
#  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的
# 位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 
# 
#  如果链表中存在环，则返回 true 。 否则，返回 false 。 
# 
#  
# 
#  进阶： 
# 
#  你能用 O(1)（即，常量）内存解决此问题吗？ 
# 
#  
# 
#  示例 1： 
# 
#  
# 
#  输入：head = [3,2,0,-4], pos = 1
# 输出：true
# 解释：链表中有一个环，其尾部连接到第二个节点。
#  
# 
#  示例 2： 
# 
#  
# 
#  输入：head = [1,2], pos = 0
# 输出：true
# 解释：链表中有一个环，其尾部连接到第一个节点。
#  
# 
#  示例 3： 
# 
#  
# 
#  输入：head = [1], pos = -1
# 输出：false
# 解释：链表中没有环。
#  
# 
#  
# 
#  提示： 
# 
#  
#  链表中节点的数目范围是 [0, 104] 
#  -105 <= Node.val <= 105 
#  pos 为 -1 或者链表中的一个 有效索引 。 
#  
#  Related Topics 链表 双指针 
#  👍 1043 👎 0


from typing import List


class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None:
            return False
        fast, slow = head, head
        while fast:
            slow = slow.next
            if fast.next is None:
                return False
            else:
                fast = fast.next.next
            if fast == slow:
                return True
        return False


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


#
# hashset 储存经过的节点, 判断节点是否存在
# def hasCycle(self, head: ListNode) -> bool:
#     d = {}
#     while head is not None:
#         if head in d:
#             return True
#         else:
#             d[head] = 1
#         head = head.next
#     return False
#     快慢指针
#     def hasCycle(self, head: ListNode) -> bool:
#         if head is None:
#             return False
#         slow = head
#         fast = head.next
#         while slow != fast:
#             # 快指针已经结束
#             if fast is None or fast.next is None:
#                 return False
#             slow = slow.next
#             fast = fast.next.next
#         return True

# 快慢指针, 同一节点
#     def hasCycle(self, head: ListNode) -> bool:
#         if head is None:
#             return False
#         fast, slow = head, head
#         while fast:
#             slow = slow.next
#             if fast.next is None:
#                 return False
#             else:
#                 fast = fast.next.next
#             if fast == slow:
#                 return True
#         return False

"""
快慢指针 : 快指针一步走两格, 慢指针一步走一格, 如果相遇, 有环; 如果快指针已到结尾, 则无环
在head之前的虚拟节点出发, 则 slow 开始为 head, fast 开始为 head.next
1-2-3
"""

if __name__ == '__main__':
    s = Solution()
    h1 = ListNode(1)
    h2 = ListNode(2)
    h1.next = h2
    h2.next = h1
    assert s.hasCycle(h1)
